A method for encoding multiword information by wordwise interleaving and error protection, with error locative clues derived from high protectivity words and directed to low protectivity words, a method for decoding such information, a device for encoding and/or decoding such information, and a carrier provided with such information.
The invention relates to a method of encoding multibit information in the form of multibit symbols arranged in relative contiguity with respect to a medium, and in particular to such a method which provides wordwise interleaving, wordwise error protection coding, and error locative clues across multiword groups. U.S. Pat. Nos. 4,559,625 to Berlekamp et al and 5,299,208 to Blaum et al disclose the decoding of interleaved and error protected information, wherein an error pattern found in a first word may give a clue to locate errors in another word of the same group of words. Errors pointed at are relatively closer or more contiguous than other symbols of the word that would generate the clue. The references use a standardized format and a fault model with multisymbol error bursts across various words. Occurrence of an error in a particular word gives a strong probability for an error to occur in a symbol position pointed at in a next word or words. The procedure will often raise the number of corrected errors.
The present inventors have recognized a problem with this method: a clue will only materialize when the clue word has been fully corrected. They have recognized a further problem: complete decoding necessitates a whole block, even if only a tiny part thereof were afflicted with errors. Combining this with a mechanically driven carrier will cause an appreciable latency, which for a disc would average about one revolution.
A object of the present invention to provide a coding format wherein clue words will be correctly decoded with a greater degree of certainty than a target word. Now therefore, according to one of its aspects the invention is characterized by the steps of splitting the multiword information into clue words and target words, providing a high level of error protection to the clue words, and a lower level of protection for said target words, and using detected errors in the clue words to identify locations in the target words having a high likelihood of error. A clue or a combination of clues, once found, symbols which may be unreliable one or more symbols which may be unreliable. With such identifying, such as by characterizing as erasure symbols, error correction will become more powerful. Many codes will correct at most t errors when no error locations are known. Given one or more erasure locations, generally a larger number e greater than t of erasures may be corrected. Other types of identifying than characterizing as erasure symbols are feasible. Protection against a combination of bursts and random errors will also improve. Alternatively, the providing of erasure locations will need the use of only a lower number of syndrome symbols, thus simplifying the calculation. The invention may be used in a storage environment as well as in a transmission environment.
It is a further object of the invention to diminish the above latency for the rather common situation that the errors are sparse. According to a solution therefor, in a storage device having a plurality of sectors in a revolution latency will often reduce to about a single sector.
The invention also relates to a method for decoding information so encoded, to an encoding and/or decoding device for use with the above method, and to a carrier provided with information for interfacing to such encoding and/or decoding.